import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-19
 * Time: 23:36
 */
public class Solution {

    /**
     *  二分查找
     *  如何确定 最后返回的 Left 一定是矩阵中含有的元素呢
     *  如果 num >= k，那么说明最终答案 x <= mid；如果 num < k，
     *  那么说明最终答案 x > mid。
     *  最后一次迭代时，check返回的结果为false，即 num < k，说明 x > mid，
     *  又因为 x <= right。当 left = mid + 1 后，left > righ，
     *  while循环结束。此时有 mid < x <= right < left = mid + 1，
     *  即 mid < x <= mid + 1。可得 x = mid + 1 = left。
     */
    public int kthSmallest(int[][] matrix, int k) {
        int len = matrix.length;
        int left = matrix[0][0];
        int right = matrix[len-1][len-1];
        while (left < right) {
            int mid = ((right-left)>>1) + left;
            if (getCount(matrix, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int getCount(int[][] matrix, int value) {
        int count = 0;
        int len = matrix.length;
        int index = 0;
        for (int i = len-1; i >= 0; i--) {
            while (index < len && matrix[i][index] <= value) {
                index++;
            }
            count += index;
        }
        return count;
    }


    /**
     *  方法二： 多路归并
     *  对 n 行同时进行归并
     *  同时对 n 行进行比较， 使用堆 更快
     *  所以 用大小为 n 的堆 存储 n 个数组
     *  但是进行判定时，每个数组的进度又不一样， 怎么办
     *  那就不直接记录数组，而是记录每个数组当然最小的值， 以及对应的下标
     *  每次数组弹出来一个值之后， 就将它的下一个元素及其位置添加进去。
     *  这样就能动态记录每个数组的进度
     */
    public int kthSmallest2(int[][] matrix, int k) {
        int len = matrix.length;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        for (int i = 0; i < len; i++) {
            minHeap.offer(new int[]{matrix[i][0], i, 0});
        }

        for (int i = 0; i < k-1; i++) {
            int[] poll = minHeap.poll();
            // 判断这一行是否已经排除完了
            if (poll[2] != len-1) {
                minHeap.offer(new int[]{matrix[poll[1]][poll[2]+1], poll[1], poll[2]+1});
            }
        }
        return minHeap.poll()[0];
    }


}